Unusual patterns of recombination emission from gas ionized by metal-free stars may distinguish early star-forming galaxies from their present-day counterparts. This pattern arises from the harder ionizing spectrum expected from metal-free stars, which strongly enhances the strength of He II recombination lines. Our calculations indicate that line fluxes of He II 1640 and 4686 are sufficiently large to be detected by narrowband and spectroscopic searches for high-redshift emission-line sources at redshift z ~ 5 using current instruments. An unknown fraction of Lya emitters may harbor low-metallicity or metal-free stars. As the predicted He II 1640 flux is comparable to and may exceed hydrogen Lya, searches for high-redshift galaxies should consider He II recombination lines as possible identifications for single emission lines in observed spectra. Spectra of metal-free stars may show both H I and He II emission lines, improving the constraints on their redshift and identification. We assess the considerable uncertainties that affect our expectations for the detection and identification of true first-generation stars with present search techniques, including the role of stellar mass loss in spectral evolution and the confusion of ionization by primordial stellar sources and AGN in the early universe.